package solution.s_763;

import java.util.*;

/**
 * 解题思路：
 *      首先获取到每个元素最后的位置。
 *      然后遍历字符串，当前元素所在的片段的结束位置 partEnd，一定是大于等于当前元素的最后出现的位置 eleEnd，即 partEnd >= eleEnd。因此 partEnd = min(partEnd, eleEnd)。
 *      一直往下遍历，直到便利到 partEnd 的位置，则表示该片段结束。
 *      再从下一个元素开始遍历，知道整个字符串遍历完。
 */
public class Solution20201022 {
    public List<Integer> partitionLabels(String S) {
        List<Integer> result = new ArrayList<>();
        if (S == null || S.length() <= 0) { return result; }

        // 查找每个元素最后出现的位置
        Map<Character, Integer> locationMap = new HashMap<>();
        for (int i = 0; i < S.length(); i ++) {
            locationMap.put(S.charAt(i), i);
        }

        int curPartLength = 0;
        int partEnd = 0;
        // 第二次遍历字符串
        for (int i = 0; i < S.length(); i ++) {
            char c = S.charAt(i);
            int lastLocation = locationMap.get(c);
            partEnd = Math.max(partEnd, lastLocation);
            curPartLength ++;

            if (partEnd == i) {
                // 如果 partEnd 与 i 相同，表示已经遍历到当前片段最后的位置
                // 记录当前片段的长度，并且重新开始计算片段长度。
                result.add(curPartLength);
                curPartLength = 0;
            }
        }

        return result;
    }
}
